{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Push Dominoes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pushDominoes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #推多米诺"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>n</code> 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。</p>\n",
    "\n",
    "<p>每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。</p>\n",
    "\n",
    "<p>如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。</p>\n",
    "\n",
    "<p>就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。</p>\n",
    "\n",
    "<p>给你一个字符串 <code>dominoes</code> 表示这一行多米诺骨牌的初始状态，其中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>dominoes[i] = 'L'</code>，表示第 <code>i</code> 张多米诺骨牌被推向左侧，</li>\n",
    "\t<li><code>dominoes[i] = 'R'</code>，表示第 <code>i</code> 张多米诺骨牌被推向右侧，</li>\n",
    "\t<li><code>dominoes[i] = '.'</code>，表示没有推动第 <code>i</code> 张多米诺骨牌。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回表示最终状态的字符串。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dominoes = \"RR.L\"\n",
    "<strong>输出：</strong>\"RR.L\"\n",
    "<strong>解释：</strong>第一张多米诺骨牌没有给第二张施加额外的力。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/05/18/domino.png\" style=\"height: 196px; width: 512px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>dominoes = \".L.R...LR..L..\"\n",
    "<strong>输出：</strong>\"LL.RR.LLRRLL..\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == dominoes.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>dominoes[i]</code> 为 <code>'L'</code>、<code>'R'</code> 或 <code>'.'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [push-dominoes](https://leetcode.cn/problems/push-dominoes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [push-dominoes](https://leetcode.cn/problems/push-dominoes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"RR.L\"', '\".L.R...LR..L..\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        od = \"\"\n",
    "        while dominoes != od:\n",
    "            od = dominoes\n",
    "            dominoes = dominoes.replace(\"R.L\", \"T\")\n",
    "            dominoes = dominoes.replace(\".L\", \"LL\")\n",
    "            dominoes = dominoes.replace(\"R.\", \"RR\")\n",
    "            dominoes = dominoes.replace(\"T\", \"R.L\")\n",
    "        return dominoes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        mask = []\n",
    "        n = len(dominoes)\n",
    "        for i, d in enumerate(dominoes):\n",
    "            if d != '.':\n",
    "                mask.append((i, d))\n",
    "        dominoes = list(dominoes)\n",
    "        for i, (x, y) in enumerate(mask):\n",
    "            if y == 'L':\n",
    "                if i:\n",
    "                    if mask[i-1][1] == 'R':\n",
    "                        for j in range((x - mask[i-1][0]) >> 1):\n",
    "                            dominoes[x - j] = 'L'\n",
    "                    else:\n",
    "                        for j in range(x - mask[i-1][0]):\n",
    "                            dominoes[x - j] = 'L'\n",
    "                else:\n",
    "                    if x:\n",
    "                        for j in range(x):\n",
    "                            dominoes[x - j] = 'L'\n",
    "            else:\n",
    "                if i + 1 < len(mask):\n",
    "                    if mask[i+1][1] == 'L':\n",
    "                        for j in range((mask[i+1][0] - x) >> 1):\n",
    "                            dominoes[x + j] = 'R'\n",
    "                    else:\n",
    "                        for j in range(mask[i+1][0] - x):\n",
    "                            dominoes[x + j] = 'R'\n",
    "                else:\n",
    "                    if x < n:\n",
    "                        for j in range(n - x):\n",
    "                            dominoes[x + j] = 'R'\n",
    "        print(dominoes)\n",
    "        return ''.join(dominoes)\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        tmp = \"\"\n",
    "        while dominoes != tmp:\n",
    "            tmp = dominoes\n",
    "            dominoes = dominoes.replace(\"R.L\", \"T\")\n",
    "            dominoes = dominoes.replace(\".L\", \"LL\")\n",
    "            dominoes = dominoes.replace(\"R.\", \"RR\")\n",
    "            dominoes = dominoes.replace(\"T\", \"R.L\")\n",
    "        return dominoes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        tmp = \"\"\n",
    "        while dominoes != tmp:\n",
    "            tmp = dominoes\n",
    "            dominoes = dominoes.replace(\"R.L\", \"T\")\n",
    "            dominoes = dominoes.replace(\".L\", \"LL\")\n",
    "            dominoes = dominoes.replace(\"R.\", \"RR\")\n",
    "            dominoes = dominoes.replace(\"T\", \"R.L\")\n",
    "        return dominoes\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        pre, ret = (-1, 'L'), ''\n",
    "        for i, s in enumerate(dominoes + 'R'):\n",
    "            if s == 'L':\n",
    "                if pre[1] == 'L':\n",
    "                    ret += 'L' * (i - pre[0])\n",
    "                else:\n",
    "                    div, mod = divmod(i - pre[0] - 1, 2)\n",
    "                    ret += 'R' * div + '.' * mod + 'L' * (div + 1)\n",
    "                pre = (i, s)\n",
    "            elif s == 'R':\n",
    "                if pre[1] == 'L':\n",
    "                    ret += '.' * (i - pre[0] - 1) + 'R'\n",
    "                else:\n",
    "                    ret += 'R' * (i - pre[0])\n",
    "                pre = (i, s)\n",
    "        return ret[:-1]        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        ans = list(dominoes)\n",
    "        n = len(dominoes)\n",
    "        i, l = 0, 'L'\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and dominoes[j] == '.':\n",
    "                j += 1\n",
    "            r = dominoes[j] if j < n else 'R'\n",
    "            if l == r: # 方向相同，这堆连续的骨牌会倒向同一方向\n",
    "                while i < j:\n",
    "                    ans[i] = l\n",
    "                    i += 1\n",
    "            elif l == 'R' and r == 'L': # 方向相对，向中间倒\n",
    "                k = j-1\n",
    "                while i < k:\n",
    "                    ans[i], ans[k] = 'R', 'L'\n",
    "                    i += 1\n",
    "                    k -= 1\n",
    "            # else: 方向相背，不倒\n",
    "            l = r\n",
    "            i = j+1\n",
    "        return ''.join(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n = len(dominoes)\n",
    "        i = 0\n",
    "        res = list(dominoes)\n",
    "        pre = 'L'\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and dominoes[j] == '.': \n",
    "                j += 1\n",
    "            right = dominoes[j] if j < n else 'R'\n",
    "            if pre == right:\n",
    "                while i < j:\n",
    "                    res[i] = right\n",
    "                    i += 1\n",
    "            elif pre == 'R' and right == 'L':\n",
    "                k = j - 1\n",
    "                while i < k:\n",
    "                    res[i] = pre\n",
    "                    res[k] = right\n",
    "                    i += 1\n",
    "                    k -= 1\n",
    "            pre = right\n",
    "            i = j + 1\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n = len(dominoes)\n",
    "        i = 0\n",
    "        res = list(dominoes)\n",
    "        pre = 'L'\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and dominoes[j] == '.': \n",
    "                j += 1\n",
    "            right = dominoes[j] if j < n else 'R'\n",
    "            if pre == right:\n",
    "                while i < j:\n",
    "                    res[i] = right\n",
    "                    i += 1\n",
    "            elif pre == 'R' and right == 'L':\n",
    "                k = j - 1\n",
    "                while i < k:\n",
    "                    res[i] = pre\n",
    "                    res[k] = right\n",
    "                    i += 1\n",
    "                    k -= 1\n",
    "            pre = right\n",
    "            i = j + 1\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        l, r = 0, 0\n",
    "        n = len(dominoes)\n",
    "        res = [c for c in dominoes]\n",
    "        while r != n:\n",
    "            if res[r] == \"R\":\n",
    "                if res[l] == \"R\":\n",
    "                    while l < r:\n",
    "                        res[l] = \"R\"\n",
    "                        l += 1\n",
    "                else:\n",
    "                    l = r \n",
    "            elif res[r] == \"L\":\n",
    "                if res[l] == \"R\":\n",
    "                    start = l\n",
    "                    while l != r:\n",
    "                        if (r - start - 1) % 2 == 1 and l == start + (r - start) // 2:\n",
    "                            l += 1\n",
    "                            continue\n",
    "                        if l <= start + (r - start) // 2:\n",
    "                            res[l] = \"R\"\n",
    "                        elif l > start + (r - start) // 2:\n",
    "                            res[l] = \"L\"\n",
    "                        l += 1\n",
    "                else:\n",
    "                    while l != r:\n",
    "                        res[l] = \"L\"\n",
    "                        l += 1\n",
    "            r += 1\n",
    "        if res[l] == \"R\" and l < n:\n",
    "            while l < n:\n",
    "                res[l] = \"R\"\n",
    "                l += 1\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dominoes = list(dominoes)\n",
    "        last_flag = ''\n",
    "        cnt = 0\n",
    "        for i in range(len(dominoes)):\n",
    "            if dominoes[i] not in 'LR':\n",
    "                cnt += 1\n",
    "            if dominoes[i] == 'R':\n",
    "                if not last_flag:\n",
    "                    cnt = 0\n",
    "                    last_flag = 'R'\n",
    "                elif last_flag == 'R':\n",
    "                    for j in range(i-cnt,i):\n",
    "                        dominoes[j] = 'R'\n",
    "                    cnt = 0\n",
    "                elif last_flag == 'L':\n",
    "                    cnt = 0\n",
    "                    last_flag = 'R'\n",
    "            if dominoes[i] == 'L':\n",
    "                print(i,i-cnt, i-cnt + cnt//2,i-cnt//2)\n",
    "                if not last_flag:\n",
    "                    for j in range(i-cnt,i):\n",
    "                        dominoes[j] = 'L'\n",
    "                    last_flag = 'L'\n",
    "                elif last_flag == 'R':\n",
    "                    for j in range(i-cnt, i-cnt + cnt//2):\n",
    "                        dominoes[j] = 'R'\n",
    "                    for j in range(i-cnt//2, i):\n",
    "                        dominoes[j] = 'L'\n",
    "                    cnt = 0\n",
    "                elif last_flag == 'L':\n",
    "                    for j in range(i-cnt,i):\n",
    "                        dominoes[j] = 'L'\n",
    "                    cnt = 0\n",
    "                last_flag = 'L'\n",
    "        if cnt and last_flag == 'R':\n",
    "            for i in range(len(dominoes) - cnt, len(dominoes)):\n",
    "                dominoes[i] = 'R'\n",
    "        return ''.join(dominoes)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        if len(dominoes) ==1:\n",
    "            return dominoes\n",
    "        if '.'*len(dominoes)==dominoes:\n",
    "            return dominoes\n",
    "        i , j  = 0,1\n",
    "        while True:\n",
    "            if dominoes[i] == '.' :\n",
    "                if  dominoes[j] == '.':\n",
    "                    j=j+1#\n",
    "                    if len(dominoes) == j:\n",
    "                        if dominoes[i-1] == 'R':\n",
    "                            dominoes = dominoes[:i] + 'R'*(j-i)\n",
    "                        break\n",
    "                    continue\n",
    "                if dominoes[j] == 'L' and i ==0:\n",
    "                    dominoes = 'L'*(j-i) + dominoes[j:]\n",
    "                if dominoes[i-1] == 'R' and dominoes[j] == 'R' and i>0: \n",
    "                    dominoes = dominoes[:i-1]+'R'*(j-i+1)+dominoes[j:]\n",
    "                if dominoes[i-1] == 'L' and dominoes[j] == 'L' and i>0: \n",
    "                    dominoes = dominoes[:i-1]+'L'*(j-i+1)+dominoes[j:]\n",
    "                if dominoes[i-1] == 'R' and dominoes[j] == 'L' and i>0: \n",
    "                    if  (j-i)%2 != 0:\n",
    "                        dominoes = dominoes[:i] + 'R'*int((j-i-1)/2) + '.' + 'L'*int(((j-i-1)/2))+ dominoes[j:]\n",
    "                    else:\n",
    "                        dominoes = dominoes[:i] + 'R'*int((j-i)/2) + 'L'*int((j-i)/2) + dominoes[j:]\n",
    "            i = j\n",
    "            j = j+1\n",
    "            if dominoes[i] == '.' and j == len(dominoes):\n",
    "                if dominoes[i-1] == 'R':\n",
    "                    dominoes = dominoes[:i] + 'R'*(j-i)\n",
    "            if len(dominoes) == j :\n",
    "                break\n",
    "        return dominoes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n: int = len(dominoes)\n",
    "        # left[i] 表示第 i 个骨牌会在第 left[i] 秒时受到向左的外力。\n",
    "        # n 表示不会受到向左的外力，方便后续统一处理。\n",
    "        # 初始化长度为 n + 1 ，方便处理最右侧为 '.' 的边界情况。\n",
    "        left: List[int] = [n] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            match dominoes[i]:\n",
    "                # 如果初始向左推动，则第 0 秒就受到向左的外力\n",
    "                case 'L': left[i] = 0\n",
    "                # 如果初始向右推动，则不会受到向左的外力\n",
    "                #（由于都初始化为 n ，可以不用再进行赋值）\n",
    "                case 'R': left[i] = n\n",
    "                # 如果右侧有骨牌初始为受到向左外力，则其会在第 left[i + 1] + 1 秒传导过来。\n",
    "                # 与 n 取最小值保证表示没有向右的外力的情况只有一种，方便后续处理。\n",
    "                case '.': left[i] = min(n, left[i + 1] + 1)\n",
    "                # 题目数据保证不存在其他情况\n",
    "\n",
    "        # ans[i] 表示第 i 个骨牌的最终状态，初始化都为竖直状态\n",
    "        ans: List[str] = ['.'] * n\n",
    "        # right 表示第 i 个骨牌会在第 right 秒时受到向右的外力。\n",
    "        # 初始化为 n ，表示第 -1 个骨牌不会受到向右的外力，\n",
    "        # 方便处理最左侧为 '.' 的边界情况。\n",
    "        right: int = n\n",
    "        for i in range(n):\n",
    "            match dominoes[i]:\n",
    "                # 如果初始向右推动，则第 0 秒就受到向右的外力\n",
    "                case 'R': right = 0\n",
    "                # 如果初始向左推动，则不会受到向右的外力\n",
    "                # （注意，此时要将 right 重置为 n ，抵消前面向右传导的外力）\n",
    "                case 'L': right = n\n",
    "                # 如果左侧有骨牌初始为受到向右外力，则其会在第 right + 1 秒传导过来。\n",
    "                # 与 n 取最小值保证表示没有向右的外力的情况只有一种，方便后续处理。\n",
    "                case '.': right = min(n, right + 1)\n",
    "                # 题目数据保证不存在其他情况\n",
    "\n",
    "            if left[i] < right:\n",
    "                # 如果向左的外力先到，则其向左倒下\n",
    "                ans[i] = 'L'\n",
    "            elif left[i] > right:\n",
    "                # 如果向右的外力先到，则其向右倒下\n",
    "                ans[i] = 'R'\n",
    "            # left[i] == right 时，左右两边的力同时到达，则相互抵消，保持竖直\n",
    "\n",
    "        # 转成字符串返回\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        res = []\n",
    "        temp = 0\n",
    "        leftdom = ''\n",
    "        size = len(dominoes)\n",
    "        for index in range(size):\n",
    "            if dominoes[index] != '.':\n",
    "                if temp:\n",
    "                    if (dominoes[index] == 'R' and (leftdom == 'L' or leftdom == '')):\n",
    "                        res.append('.' * temp)\n",
    "                    elif leftdom == 'R' and dominoes[index] == 'L':\n",
    "                        res.append('R' * int(temp / 2) + '.' * (temp % 2) + 'L' * int(temp / 2))\n",
    "                    elif (leftdom == 'L' or leftdom == '') and dominoes[index] == 'L':\n",
    "                        res.append('L' * temp)\n",
    "                    elif leftdom == 'R' and dominoes[index] == 'R':\n",
    "                        res.append('R' * temp)\n",
    "                    temp = 0\n",
    "                res.append(dominoes[index])\n",
    "                leftdom = dominoes[index]\n",
    "            else:\n",
    "                temp += 1\n",
    "                if index == size - 1:\n",
    "                    if leftdom == 'R':\n",
    "                        res.append('R' * temp)\n",
    "                    else:\n",
    "                        res.append('.' * temp)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pushDominoes(self, d):\n",
    "        d = \"L\" + d + \"R\"\n",
    "        res = []\n",
    "        l = 0\n",
    "        for r in range(1, len(d)):\n",
    "            if d[r] == '.':\n",
    "                continue\n",
    "            mid = r - l - 1\n",
    "            if l: # 虚拟的牌不放入结果\n",
    "                res.append(d[l])\n",
    "            if mid > 0:\n",
    "                if d[l] == d[r]:\n",
    "                    res.append(d[l] * mid)\n",
    "                elif d[l] == 'L' and d[r] == 'R':\n",
    "                    res.append('.' * mid)\n",
    "                else:\n",
    "                    res.append('R' * (mid // 2) + '.' * (mid % 2) + 'L' * (mid // 2))\n",
    "            l = r\n",
    "            # print(mid, l, r)\n",
    "            # print(r, res)\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dominoes = list(dominoes)\n",
    "        dominoes = ['L'] + dominoes + ['R']\n",
    "\n",
    "        i = 0\n",
    "        n = len(dominoes)\n",
    "        while i < n - 1:\n",
    "            if dominoes[i] == '.':\n",
    "                pos = i + 1\n",
    "                while dominoes[pos] == '.':\n",
    "                    pos += 1\n",
    "\n",
    "                if dominoes[i - 1] == dominoes[pos]:\n",
    "                    dominoes[i: pos] = [dominoes[pos]] * (pos - i)\n",
    "                elif dominoes[i - 1] == 'R' and dominoes[pos] == 'L':\n",
    "                    diff = pos - i\n",
    "                    mid = int(diff / 2)\n",
    "                    dominoes[i: i + mid] = ['R'] * mid\n",
    "                    dominoes[pos - mid: pos] = ['L'] * mid\n",
    "                \n",
    "                i = pos + 1\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        return (''.join(dominoes[1:-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        status = 'L'\n",
    "        status_index = -1\n",
    "        dominoes = dominoes + 'R'\n",
    "        ans_list = ['.' for _ in dominoes]\n",
    "        for i, domino in enumerate(dominoes):\n",
    "            if domino == status:\n",
    "                for j in range(status_index + 1, i + 1):\n",
    "                    ans_list[j] = status\n",
    "                status_index = i\n",
    "            elif domino == 'R':\n",
    "                ans_list[i] = domino\n",
    "                status = domino\n",
    "                status_index = i\n",
    "            elif domino == 'L':\n",
    "                left_mid = (status_index + i + 1) // 2 - 1\n",
    "                right_mid = (status_index + i) // 2 + 1\n",
    "                for j in range(status_index + 1, left_mid + 1):\n",
    "                    ans_list[j] = status\n",
    "                for j in range(right_mid, i + 1):\n",
    "                    ans_list[j] = domino\n",
    "                status = domino\n",
    "                status_index = i\n",
    "        return ''.join(ans_list[:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        # n = len(dominoes)\n",
    "        # left = [0]*n\n",
    "        # right = [0]*n\n",
    "\n",
    "        \n",
    "        # l = 0\n",
    "        # r = 0\n",
    "        # while l<n:\n",
    "        #     if dominoes[l]=='R':\n",
    "        #         while r<n and dominoes[r]!='L' :\n",
    "        #             if dominoes[r]=='R':\n",
    "        #                 right[r] = 1\n",
    "        #             elif dominoes[r]=='.':\n",
    "        #                 right[r] = right[r-1]+1\n",
    "        #             r += 1\n",
    "        #         l = r\n",
    "        #     else:\n",
    "        #         l += 1\n",
    "        #         r = l\n",
    "        # l = n-1\n",
    "        # r = n-1\n",
    "        # while r>=0:           \n",
    "        #     if dominoes[r]=='L':\n",
    "        #         while l>=0 and dominoes[l]!='R':\n",
    "        #             if dominoes[l]=='L':\n",
    "        #                 left[l] = 1\n",
    "        #             elif dominoes[l]=='.':\n",
    "        #                 left[l] = left[l+1] + 1\n",
    "        #             l -= 1\n",
    "        #         r = l\n",
    "        #     else:\n",
    "        #         r -= 1\n",
    "        #         l = r\n",
    "        \n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        # res = []\n",
    "        # for i in range(n):\n",
    "        #     if left[i] and not right[i]:\n",
    "        #         res.append('L')\n",
    "        #     elif right[i] and not left[i]:\n",
    "        #         res.append('R')\n",
    "        #     elif not left[i] and not right[i]:\n",
    "        #         res.append('.')\n",
    "        #     else:\n",
    "        #         if left[i]>right[i]:\n",
    "        #             res.append('R')\n",
    "        #         elif right[i]>left[i]:\n",
    "        #             res.append('L')\n",
    "        #         else:\n",
    "        #             res.append('.')\n",
    "\n",
    "        # return \"\".join(res)\n",
    "\n",
    "        d = \"L\" + dominoes + \"R\"\n",
    "        res = []\n",
    "        l = 0\n",
    "        for r in range(1, len(d)):\n",
    "            if d[r]=='.':\n",
    "                continue \n",
    "            if l:\n",
    "                res.append(d[l])\n",
    "            mid = r-l-1\n",
    "            if d[l]==d[r]:\n",
    "                res.append(d[l]*mid)\n",
    "            elif d[l]=='L' and d[r]=='R':\n",
    "                res.append('.'*mid)\n",
    "            else:\n",
    "                res.append('R'*(mid//2)+'.'*(mid%2)+'L'*(mid//2))\n",
    "            l = r\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "\n",
    "        d = \"L\" + dominoes + \"R\"\n",
    "        res = []\n",
    "        l = 0\n",
    "        for r in range(1, len(d)):\n",
    "            if d[r] == \".\":\n",
    "                continue\n",
    "            mid = r - l - 1\n",
    "            if l:\n",
    "                res.append(d[l])\n",
    "\n",
    "            if d[l] == d[r]:\n",
    "                res.append(d[l] * mid)\n",
    "            elif d[l] == \"L\" and d[r] == \"R\":\n",
    "                res.append(\".\" * mid)\n",
    "            else:\n",
    "\n",
    "                res.append('R' * ( mid // 2) + \".\" * (mid % 2) + 'L' * (mid // 2))\n",
    "            l = r\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "\n",
    "\n",
    "        d = \"L\" + dominoes + \"R\"\n",
    "\n",
    "        res = []\n",
    "\n",
    "        l = 0\n",
    "\n",
    "        for r in range(1, len(d)):\n",
    "            if d[r] == \".\":\n",
    "                continue\n",
    "\n",
    "            mid = r - l - 1\n",
    "\n",
    "            if l:\n",
    "\n",
    "                res.append(d[l])\n",
    "\n",
    "            if d[l] == d[r]:\n",
    "                res.append(d[l] * mid)\n",
    "            elif d[l] == \"L\" and d[r] == \"R\":\n",
    "                res.append(\".\" * mid)\n",
    "            else:\n",
    "\n",
    "                res.append('R' * ( mid // 2) + \".\" * (mid % 2) + 'L' * (mid // 2))\n",
    "            l = r\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        ans = []\n",
    "        last = 'L'\n",
    "        cnt = 0\n",
    "        for c in dominoes:\n",
    "            if c == '.':\n",
    "                cnt += 1\n",
    "                continue\n",
    "            if c == 'L':\n",
    "                if last == 'L':\n",
    "                    ans.append('L' * cnt)\n",
    "                else:\n",
    "                    x = cnt >> 1\n",
    "                    ans.append('R' * x + '.' * (cnt & 1) + 'L' * x)\n",
    "            else:\n",
    "                if last == 'R':\n",
    "                    ans.append('R' * cnt)\n",
    "                else:\n",
    "                    ans.append('.' * cnt)\n",
    "            cnt = 0\n",
    "            last = c\n",
    "            ans.append(c)\n",
    "        if last == 'R':\n",
    "            ans.append('R' * cnt)\n",
    "        else:\n",
    "            ans.append('.' * cnt)\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        ### \n",
    "        ##  模拟题\n",
    "        s = list(dominoes)\n",
    "        n = len(dominoes)\n",
    "        last ='L'\n",
    "        cnt = 0\n",
    "        ans=[]\n",
    "        for  c in dominoes:\n",
    "            if c == '.':\n",
    "                cnt +=1\n",
    "                continue\n",
    "\n",
    "            elif c =='L':\n",
    "                if last =='L':\n",
    "                    ans.append('L'*cnt)\n",
    "                else:\n",
    "                    x = cnt >>1\n",
    "                    ans.append('R'*x+ '.'*(cnt&1) + 'L'*x)\n",
    "            else:\n",
    "                #R\n",
    "                if last=='R':\n",
    "                    ans.append('R'*cnt)\n",
    "                else:\n",
    "                    ans.append( '.'*cnt)\n",
    "            cnt = 0\n",
    "            last =c\n",
    "            ans.append(c)\n",
    "        if last =='R':\n",
    "            ans.append('R'*cnt)\n",
    "        else :\n",
    "            ans.append('.'*cnt)\n",
    "        return ''.join(ans) \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict, deque\n",
    "from bisect import bisect_left, bisect_right\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        \"\"\"\n",
    "\n",
    "        :param dominoes:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        pos = []\n",
    "        ok = False\n",
    "        cache = ''\n",
    "        if '.' * len(dominoes) == dominoes:\n",
    "            return dominoes\n",
    "        idx1 = 0\n",
    "        for i in dominoes:\n",
    "            if i != '.':\n",
    "                break\n",
    "            cache += '.'\n",
    "            idx1 += 1\n",
    "        cache2 = ''\n",
    "        for i in  range(len(dominoes)-1, -1, -1):\n",
    "            if dominoes[i] != '.':\n",
    "                break\n",
    "            cache2 += '.'\n",
    "        dominoes = dominoes[idx1:len(dominoes)-len(cache2)]\n",
    "\n",
    "        if dominoes[0] == 'L':\n",
    "            cache = 'L' * len(cache)\n",
    "        if dominoes[-1] == 'R':\n",
    "            cache2 = 'R' * len(cache2)\n",
    "\n",
    "\n",
    "        idxlist = []\n",
    "        for k,v in enumerate(dominoes):\n",
    "            if v != '.':\n",
    "                idxlist.append(k)\n",
    "\n",
    "        ret = ''\n",
    "        for k,v in enumerate(dominoes):\n",
    "            if v != '.':\n",
    "                ret += v\n",
    "                next1 = bisect_right(idxlist, k)\n",
    "                next1 = min(next1, len(idxlist)-1)\n",
    "                if k == idxlist[next1]:\n",
    "                    continue\n",
    "                gapl = idxlist[next1] - k\n",
    "                if gapl == 1:\n",
    "\n",
    "                    continue\n",
    "                if v == 'L':\n",
    "                    if dominoes[idxlist[next1]] == 'L':\n",
    "                        ret += 'L' * (gapl -1)\n",
    "                    else:\n",
    "                        ret +=  '.' * (gapl-1)\n",
    "\n",
    "                if v == 'R':\n",
    "                    if dominoes[idxlist[next1]] == 'R':\n",
    "                        ret += 'R' * (gapl -1)\n",
    "                    else:\n",
    "                        ret += 'R' * ((gapl-1) // 2)\n",
    "                        if (gapl-1) % 2 == 1:\n",
    "                            ret += '.'\n",
    "                        ret += 'L' * ((gapl-1) // 2)\n",
    "\n",
    "        return cache + ret + cache2\n",
    "\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.pushDominoes(\".L.R...LR..L..\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        l=len(dominoes)\n",
    "        left=[inf for i in range(l)]\n",
    "        right=[inf for i in range(l)]\n",
    "        for i in range(l):\n",
    "            if dominoes[i]=='L':\n",
    "                temp=i \n",
    "                left[i]=0\n",
    "                while i-1>=0 and left[i-1]!=0 and dominoes[i-1]=='.':\n",
    "                    left[i-1]=left[i]+1 \n",
    "                    i=i-1 \n",
    "                i=temp \n",
    "        for i in range(l-1,-1,-1):\n",
    "            if dominoes[i]=='R':\n",
    "                temp=i \n",
    "                right[i]=0\n",
    "                while i+1<l and right[i+1]!=0 and dominoes[i+1]=='.':\n",
    "                    right[i+1]=right[i]+1 \n",
    "                    i=i+1 \n",
    "                i=temp \n",
    "        res=[]\n",
    "        print(left,right)\n",
    "        for i in range(l):\n",
    "            if left[i]<right[i]:\n",
    "                res.append('L')\n",
    "            elif left[i]>right[i]:\n",
    "                res.append('R')\n",
    "            else:\n",
    "                res.append('.')\n",
    "        return ''.join(res)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        trans = {\".\": 0, \"L\": 1, \"R\": -1}\n",
    "        l = []\n",
    "        r = [0 for i in range(len(dominoes))]\n",
    "        for i in range(len(dominoes)):\n",
    "            if i == 0 or trans[dominoes[i]] != 0:\n",
    "                l.append(trans[dominoes[i]])\n",
    "            elif l[i-1] >= 0:\n",
    "                l.append(0)\n",
    "            else:\n",
    "                l.append(l[-1]-1)\n",
    "        \n",
    "        for i in range(len(dominoes)-1, -1, -1):\n",
    "            if i == len(dominoes) - 1 or trans[dominoes[i]] != 0:\n",
    "                r[i] = trans[dominoes[i]]\n",
    "            elif r[i+1] <= 0:\n",
    "                r[i] = 0\n",
    "            else:\n",
    "                r[i] = r[i+1]+1\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(dominoes)):\n",
    "            if l[i] + r[i] == 0:\n",
    "                res.append(\".\")\n",
    "            elif l[i] * r[i] < 0:\n",
    "                if l[i] + r[i] < 0:\n",
    "                    res.append(\"L\")\n",
    "                else:\n",
    "                    res.append(\"R\")\n",
    "            elif l[i] + r[i] < 0:\n",
    "                res.append(\"R\")\n",
    "            else:\n",
    "                res.append(\"L\")\n",
    "\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dominoes = \"L\" + dominoes + \"R\"\n",
    "        res = []\n",
    "        l = 0\n",
    "        for r in range(1, len(dominoes)):\n",
    "            if dominoes[r] == \".\":\n",
    "                continue\n",
    "\n",
    "            m = r - l - 1\n",
    "            if l > 0:\n",
    "                res.append(dominoes[l])\n",
    "            if dominoes[l] == dominoes[r]:\n",
    "                res.append(dominoes[l] * m)\n",
    "            elif dominoes[l] == 'L' and dominoes[r] == \"R\":\n",
    "                res.append(\".\" * m)\n",
    "            else:\n",
    "                res.append(\"R\" * (m//2) + \".\"*(m%2) + \"L\"*(m//2))\n",
    "            l = r \n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pushDominoes(self, d):\n",
    "        \"\"\"\n",
    "        :type dominoes: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        d = \"L\" + d + \"R\"\n",
    "        res = []\n",
    "        l = 0\n",
    "        for r in range(1, len(d)):\n",
    "            if d[r] == '.':\n",
    "                continue\n",
    "            mid = r - l - 1\n",
    "            if l: # 虚拟的牌不放入结果\n",
    "                res.append(d[l])\n",
    "            if d[l] == d[r]:\n",
    "                res.append(d[l] * mid)\n",
    "            elif d[l] == 'L' and d[r] == 'R':\n",
    "                res.append('.' * mid)\n",
    "            else:\n",
    "                res.append('R' * (mid // 2) + '.' * (mid % 2) + 'L' * (mid // 2))\n",
    "            l = r\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, d: str) -> str:\n",
    "        d = 'L' + d + 'R'\n",
    "        res = []\n",
    "        l = 0\n",
    "        for r in range(1, len(d)):\n",
    "            if d[r] == '.': # 找到第一个右边有影响的牌\n",
    "                continue\n",
    "            mid = r - l - 1 # 不包括rl, 中间的数量\n",
    "            if l:\n",
    "                res.append(d[l])\n",
    "            \n",
    "            if d[l] == d[r]:\n",
    "                res.append(d[l] * mid)\n",
    "            elif d[l] == 'L' and d[r] == 'R':\n",
    "                res.append('.' * mid)\n",
    "            else: # R .... L\n",
    "                res.append('R' * (mid // 2))\n",
    "                res.append('.' * (mid % 2))\n",
    "                res.append('L' * (mid // 2))\n",
    "            l = r\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=838 lang=python\n",
    "#\n",
    "# [838] 推多米诺\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution(object):\n",
    "    def pushDominoes(self, dominoes):\n",
    "        \"\"\"\n",
    "        :type dominoes: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        dominoes = list(dominoes)\n",
    "        stack = []\n",
    "        for i in range(len(dominoes)):\n",
    "            if dominoes[i] != '.':\n",
    "                stack.append(i)\n",
    "        dominoes = self.bfs(dominoes, stack)\n",
    "        result = \"\"\n",
    "\n",
    "        for i in dominoes:\n",
    "            result = result + i\n",
    "        \n",
    "        return result\n",
    "    def bfs(self, dominoes, stack):\n",
    "        new_stack = []\n",
    "        while stack:\n",
    "            i = stack.pop()\n",
    "            if dominoes[i] == \"R\" and i+1 < len(dominoes):\n",
    "                if dominoes[i+1] == \".\":\n",
    "                    dominoes[i+1] = \"R\"\n",
    "                    new_stack.append(i+1)\n",
    "                elif dominoes[i+1] == \"L\" and i+1 in new_stack:\n",
    "                    dominoes[i+1] = \".\"\n",
    "                    new_stack.remove(i+1)\n",
    "            elif dominoes[i] == \"L\" and i-1 >= 0:\n",
    "                if dominoes[i-1] == \".\":\n",
    "                    dominoes[i-1] = \"L\"\n",
    "                    new_stack.append(i-1)\n",
    "                elif dominoes[i-1] == \"R\" and i-1 in new_stack:\n",
    "                    dominoes[i-1] = \".\"\n",
    "                    new_stack.remove(i-1)\n",
    "            if len(stack) == 0:\n",
    "                stack = new_stack[0:]\n",
    "                new_stack= []\n",
    "        return dominoes\n",
    "\n",
    "\n",
    "            \n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n = len(dominoes)\n",
    "        forces = [0] * n\n",
    "\n",
    "        force = 0\n",
    "        for i in range(n):\n",
    "            if dominoes[i] == 'R':\n",
    "                force = n\n",
    "            elif dominoes[i] == 'L':\n",
    "                force = 0\n",
    "            else:\n",
    "                force = max(force - 1, 0)\n",
    "            forces[i] += force\n",
    "        \n",
    "        force = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if dominoes[i] == 'L':\n",
    "                force = -n\n",
    "            elif dominoes[i] == 'R':\n",
    "                force = 0\n",
    "            else:\n",
    "                force = min(force + 1, 0)\n",
    "            forces[i] += force\n",
    "        \n",
    "        result = []\n",
    "        for force in forces:\n",
    "            if force > 0:\n",
    "                result.append('R')\n",
    "            elif force < 0:\n",
    "                result.append('L')\n",
    "            else:\n",
    "                result.append('.')\n",
    "        return ''.join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        \n",
    "        n = len(dominoes)\n",
    "        ans = list(dominoes)\n",
    "        pre_r = [-1]*n\n",
    "        ind = -1\n",
    "        for i in range(n):\n",
    "            if dominoes[i] == 'R':\n",
    "                ind = i\n",
    "            elif dominoes[i] == 'L':\n",
    "                ind = -1\n",
    "            pre_r[i] = ind\n",
    "        \n",
    "        post_l = [-1]*n\n",
    "        ind = -1\n",
    "        for i in range(n-1, -1, -1):    \n",
    "            if dominoes[i] == 'L':\n",
    "                ind = i\n",
    "            elif dominoes[i] == 'R':\n",
    "                ind = -1\n",
    "            post_l[i] = ind\n",
    "        for i in range(n):\n",
    "            if dominoes[i] == \".\":\n",
    "                left ,right = pre_r[i], post_l[i]\n",
    "                if left == -1 and right == -1:\n",
    "                    continue\n",
    "                elif left == -1:\n",
    "                    ans[i] = \"L\"    \n",
    "                elif right == -1:   \n",
    "                    ans[i] = \"R\"\n",
    "                else:\n",
    "                    if i-left > right-i:\n",
    "                        ans[i] = \"L\"\n",
    "                    elif i-left < right-i:  \n",
    "                        ans[i] = \"R\"\n",
    "                    else:\n",
    "                        ans[i] = \".\"\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        res = []\n",
    "        while True:\n",
    "            dominoes = dominoes.replace('R.L', 'R#L').replace('.L', 'LL').replace('R.', 'RR')\n",
    "            res.append(dominoes)\n",
    "            if res.count(dominoes) == 2:\n",
    "                break\n",
    "\n",
    "        return dominoes.replace('#', '.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        q = deque()\n",
    "        n = len(dominoes)\n",
    "        time = [0]*n\n",
    "        f = [0]*n\n",
    "        for i,e in enumerate(dominoes):\n",
    "            if e == '.':\n",
    "                continue\n",
    "            q.append(i)\n",
    "            f[i] = 1 if e == 'R' else -1\n",
    "            time[i] = 1\n",
    "        \n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            if f[i] != 0:\n",
    "                ni = i + f[i]\n",
    "                if 0 <= ni < n:\n",
    "                    if time[ni] == 0:\n",
    "                        q.append(ni)\n",
    "                        f[ni] = f[i]\n",
    "                        time[ni] = time[i] + 1\n",
    "                    elif time[ni] == time[i] + 1:\n",
    "                        f[ni] = 0\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if f[i] == 0:\n",
    "                res.append('.')\n",
    "            elif f[i] == 1:\n",
    "                res.append('R')\n",
    "            else:\n",
    "                res.append('L')\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        time_list = list(0 if card in ['R', 'L'] else float('inf') for card in dominoes)\n",
    "        card_list = list(dominoes)\n",
    "        q = deque()\n",
    "        for idx, card in enumerate(dominoes):\n",
    "            if card in ['R', 'L']:\n",
    "                q.append(idx)\n",
    "        while q:\n",
    "            q_len = len(q)\n",
    "            for _ in range(q_len):\n",
    "                curr_idx = q.popleft()\n",
    "                next_idx = curr_idx + 1 if card_list[curr_idx] == 'R' else curr_idx - 1\n",
    "                if next_idx < 0 or next_idx >= len(dominoes):\n",
    "                    continue\n",
    "                if time_list[curr_idx] + 1 < time_list[next_idx]:\n",
    "                    card_list[next_idx] = card_list[curr_idx]\n",
    "                    q.append(next_idx)\n",
    "                    time_list[next_idx] = time_list[curr_idx] + 1\n",
    "                elif time_list[curr_idx] + 1 == time_list[next_idx]:\n",
    "                    card_list[next_idx] = '.'\n",
    "                    # time_list[next_idx] = time_list[curr_idx]+1\n",
    "        return ''.join(card_list)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        if dominoes == \"\":\n",
    "            return \"\"\n",
    "\n",
    "        e = [0]*len(dominoes)\n",
    "        \n",
    "        \n",
    "        for i in range(len(dominoes)):\n",
    "            if dominoes[i] == 'L':\n",
    "                e[i] = -1\n",
    "            elif dominoes[i] == 'R':\n",
    "                e[i] = 1\n",
    "            else:\n",
    "                e[i] = 0\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        import copy\n",
    "        ee = copy.deepcopy(e)\n",
    "        a = []\n",
    "        while True:\n",
    "            \n",
    "        \n",
    "            for i in range(len(e)):\n",
    "                if e[i] == -1:\n",
    "                    if i-1>=0:\n",
    "                        if e[i-1]==0:\n",
    "                            ee[i-1]-=1\n",
    "                elif e[i] == 1:\n",
    "                    if i+1<len(e):\n",
    "                        if e[i + 1] == 0:\n",
    "                            ee[i+1] += 1\n",
    "        \n",
    "            for i in range(len(ee)):\n",
    "                if ee[i]>1:\n",
    "                    ee[i]=1\n",
    "                elif ee[i]<-1:\n",
    "                    ee[i]=-1\n",
    "        \n",
    "        \n",
    "            e = copy.deepcopy(ee)\n",
    "            if a == ee:\n",
    "                break\n",
    "            a = copy.deepcopy(ee)\n",
    "        \n",
    "        #print(ee)\n",
    "        eee = ''\n",
    "        for i in ee:\n",
    "            if i==-1:\n",
    "                eee+='L'\n",
    "            elif i == 1:\n",
    "                eee+='R'\n",
    "            else:\n",
    "                eee+='.'\n",
    "        return eee\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        res = []\n",
    "        while True:\n",
    "            dominoes = dominoes.replace('R.L','R*L').replace('R.','RR').replace('.L','LL')\n",
    "            res.append(dominoes)\n",
    "            # 当最新的两个 dominoes 都相同说明转换完成\n",
    "            if res.count(dominoes) >= 2:\n",
    "                break\n",
    "        return dominoes.replace('*','.')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        res = []\n",
    "        while True:\n",
    "            dominoes = dominoes.replace('R.L', 'R*L').replace('R.','RR').replace('.L','LL')\n",
    "            res.append(dominoes)\n",
    "            if res.count(dominoes) >= 2:\n",
    "                break \n",
    "        return dominoes.replace('*','.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        left = [0 for _ in dominoes]\n",
    "        right = [0 for _ in dominoes]\n",
    "\n",
    "        pre = float('inf')\n",
    "        for i in range(len(dominoes)):\n",
    "            left[i] = pre\n",
    "            if dominoes[i] == \"R\":\n",
    "                pre = 1\n",
    "            elif dominoes[i] == \"L\":\n",
    "                pre = float('inf')\n",
    "            else:\n",
    "                pre += 1\n",
    "        pre = float('inf')\n",
    "        for i in range(len(dominoes)-1, -1, -1):\n",
    "            right[i] = pre \n",
    "            if dominoes[i] == \"L\":\n",
    "                pre = 1\n",
    "            elif dominoes[i] == \"R\":\n",
    "                pre = float('inf')\n",
    "            else:\n",
    "                pre += 1\n",
    "\n",
    "        dominoes = list(dominoes)\n",
    "        for i in range(len(dominoes)):\n",
    "            if dominoes[i] == \".\":\n",
    "                if left[i] < right[i]:\n",
    "                    dominoes[i] = \"R\"\n",
    "                elif left[i] > right[i]:\n",
    "                    dominoes[i] = \"L\"\n",
    "        return ''.join(dominoes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        _dic = {i: v for i, v in enumerate(dominoes) if v != \".\"}\n",
    "        ans, tmp = list(dominoes), 0\n",
    "        for idx, val in _dic.items():\n",
    "            if ans[tmp] == \"R\" and ans[idx] == \"L\":\n",
    "                left, right = tmp, idx\n",
    "                while left < right:\n",
    "                    ans[left], ans[right] = \"R\", \"L\"\n",
    "                    left, right = left + 1, right - 1\n",
    "            elif ans[tmp] == ans[idx] or (tmp == 0 and ans[idx] == \"L\"):\n",
    "                ans[tmp: idx + 1] = [val] * (idx - tmp + 1)\n",
    "            tmp = idx\n",
    "        if ans[tmp] == \"R\":\n",
    "            ans[tmp:] = [\"R\"] * (len(ans) - tmp)\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        queue = deque()\n",
    "        dominoes_list = list(dominoes)\n",
    "        for idx, domino in enumerate(dominoes_list):\n",
    "            if domino != '.':\n",
    "                queue.append((domino, idx))\n",
    "        #print(queue)\n",
    "        n = len(dominoes_list)\n",
    "        while queue:\n",
    "            direction, idx = queue.popleft()\n",
    "            if direction == 'L' and idx > 0 and dominoes_list[idx - 1] == '.':\n",
    "                dominoes_list[idx - 1] = 'L'\n",
    "                queue.append(('L', idx - 1))\n",
    "            # if direction == 'R' and idx + 2 < n and dominoes_list[idx + 2] == 'L' and dominoes_list[idx + 1] == '.':\n",
    "            #     queue.popleft()\n",
    "            elif direction == 'R' and idx + 1 < n and dominoes_list[idx + 1] == '.':\n",
    "                if idx + 2 < n and dominoes_list[idx + 2] == 'L':\n",
    "                    queue.popleft()\n",
    "                else:\n",
    "                    dominoes_list[idx + 1] = 'R'\n",
    "                    queue.append(('R', idx + 1))\n",
    "            #print(queue, dominoes_list)\n",
    "        return ''.join(dominoes_list)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n = len(dominoes)\n",
    "        L, R = [(0, 0)] * n, [(0, 0)] * n\n",
    "        pre_left = (float(\"-inf\"), \".\")\n",
    "        for i in range(n):\n",
    "            if dominoes[i] == '.':\n",
    "                L[i] = pre_left\n",
    "            else:\n",
    "                pre_left = (i, dominoes[i])\n",
    "        pre_right = (float(\"inf\"), \".\")\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if dominoes[i] == '.':\n",
    "                R[i] = pre_right\n",
    "            else:\n",
    "                pre_right = (i, dominoes[i])\n",
    "        dominoes = list(dominoes)\n",
    "        for i in range(n):\n",
    "            if dominoes[i] != '.':\n",
    "                continue\n",
    "            if L[i][1] != \"R\":\n",
    "                if R[i][1] != \"R\":\n",
    "                    dominoes[i] = R[i][1]\n",
    "            else:\n",
    "                if R[i][1] != \"L\":\n",
    "                    dominoes[i] = L[i][1]\n",
    "                else:\n",
    "                    if i-L[i][0] > R[i][0]-i:\n",
    "                        dominoes[i] = \"L\"\n",
    "                    elif i-L[i][0] < R[i][0]-i:\n",
    "                        dominoes[i] = \"R\"\n",
    "                    else:\n",
    "                        dominoes[i] = \".\"\n",
    "        return \"\".join(dominoes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        q = deque()\n",
    "        s = list(s)\n",
    "        for i, c in enumerate(s):\n",
    "            if c == \".\": continue \n",
    "            q.append((i, c))\n",
    "        \n",
    "        while q:\n",
    "            i, d = q.popleft()\n",
    "\n",
    "            if d == \"L\" and i > 0 and s[i - 1] == \".\":\n",
    "                q.append((i - 1, \"L\"))\n",
    "                s[i - 1] = \"L\"\n",
    "            elif d == \"R\":\n",
    "                if i + 1 < n and s[i + 1] == \".\":\n",
    "                    if i + 2 < n and s[i + 2] == \"L\":\n",
    "                        q.popleft()\n",
    "                    else:\n",
    "                        q.append((i + 1, \"R\"))\n",
    "                        s[i + 1] = \"R\"\n",
    "        \n",
    "        return \"\".join(s)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "\n",
    "        n = len(dominoes)\n",
    "\n",
    "        pre = [-1]*n\n",
    "        x = -1\n",
    "        for i in range(n):\n",
    "            if dominoes[i] in \"LR\":\n",
    "                x = i\n",
    "            pre[i] = x\n",
    "\n",
    "        post = [-1]*n\n",
    "        x = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if dominoes[i] in \"LR\":\n",
    "                x = i\n",
    "            post[i] = x\n",
    "\n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            if dominoes[i] in \"LR\":\n",
    "                ans += dominoes[i]\n",
    "            else:\n",
    "                if pre[i] != -1 and post[i] != -1:\n",
    "                    left = dominoes[pre[i]]\n",
    "                    right = dominoes[post[i]]\n",
    "                    if left == \"R\" and right == \"L\":\n",
    "                        if i-pre[i] == post[i] - i:\n",
    "                            ans += \".\"\n",
    "                        elif i-pre[i] > post[i] - i:\n",
    "                            ans += \"L\"\n",
    "                        else:\n",
    "                            ans += \"R\"\n",
    "                    elif left == \"R\":\n",
    "                        ans += \"R\"\n",
    "                    elif right == \"L\":\n",
    "                        ans += \"L\"\n",
    "                    else:\n",
    "                        ans += \".\"\n",
    "                else:\n",
    "                    if pre[i] != -1:\n",
    "                        ans += \"R\" if dominoes[pre[i]] == \"R\" else \".\"\n",
    "                    elif post[i] != -1:\n",
    "                        ans += \"L\" if dominoes[post[i]] == \"L\" else \".\"\n",
    "                    else:\n",
    "                        ans += \".\"\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        d = ['L'] + list(dominoes)+['R']\n",
    "        n = len(d)\n",
    "        l, r = [-1]*n, [-1]*n\n",
    "        i, j = 0, 0\n",
    "        for i in range(n):\n",
    "            if d[i]!='.':\n",
    "                j = i\n",
    "            l[i] = j\n",
    "        \n",
    "        i, j = 0, 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if d[i]!='.':\n",
    "                j = i\n",
    "            r[i] = j\n",
    "\n",
    "        for i in range(n):\n",
    "            l_ch, r_ch = d[l[i]], d[r[i]]\n",
    "            if l_ch=='L' and r_ch=='R':\n",
    "                d[i] = '.'\n",
    "            elif l_ch=='L' and r_ch=='L':\n",
    "                d[i] = 'L'\n",
    "            elif l_ch=='R' and r_ch=='R':\n",
    "                d[i] = 'R'\n",
    "            else:\n",
    "                if i-l[i]>r[i]-i:\n",
    "                    d[i] = 'L'\n",
    "                elif i-l[i]<r[i]-i:\n",
    "                    d[i] = 'R'\n",
    "                else:\n",
    "                    d[i] = '.'\n",
    "        return \"\".join(d[1:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        L, R = [], []\n",
    "        # 找出每个点，右边（包含当前位置）第一个 L 在哪儿\n",
    "        h = []\n",
    "        for i, x in enumerate(dominoes):\n",
    "            if x == 'L' or x == 'R':\n",
    "                h.append(i)\n",
    "\n",
    "        t = 0\n",
    "        for i, x in enumerate(dominoes):\n",
    "            while t < len(h) and h[t] < i:\n",
    "                t += 1\n",
    "            \n",
    "            if t < len(h) and h[t] >= i and dominoes[h[t]] == 'L':\n",
    "                L.append(h[t] - i)\n",
    "            else:\n",
    "                L.append(float(\"inf\"))\n",
    "\n",
    "        # 找出每个点，左边（包含当前位置）第一个 R 在哪儿\n",
    "        t = 0\n",
    "        for i, x in enumerate(dominoes):\n",
    "            while True:\n",
    "                if t + 1 < len(h) and h[t+1] <= i:\n",
    "                    t += 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            if t < len(h) and h[t] <= i and dominoes[h[t]] == 'R':\n",
    "                R.append(i - h[t])\n",
    "            else:\n",
    "                R.append(float(\"inf\"))\n",
    "\n",
    "        ans = []\n",
    "        for i in range(len(dominoes)):\n",
    "            if L[i] < R[i]:\n",
    "                ans.append('L')\n",
    "            elif L[i] > R[i]:\n",
    "                ans.append('R')\n",
    "            else:\n",
    "                ans.append('.')\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dominoes = list(dominoes)\n",
    "        que = deque()\n",
    "\n",
    "        print(dominoes)\n",
    "        for i,d in enumerate(dominoes):\n",
    "            if d == 'L' or d == 'R':\n",
    "                que.append((i, d))\n",
    "            \n",
    "        while que:\n",
    "            n = len(que)\n",
    "            for _ in range(n):\n",
    "                cur, d = que.popleft()\n",
    "                if d == 'L' and cur-1 >=0:\n",
    "                    if dominoes[cur-1] == '.':\n",
    "                        dominoes[cur-1] = 'L1'# ready to fall to Left\n",
    "                    elif dominoes[cur-1] == 'R1':\n",
    "                        dominoes[cur-1] = '.'\n",
    "                if d == 'R' and cur+1 < len(dominoes):\n",
    "                    if dominoes[cur+1] == '.':\n",
    "                        dominoes[cur+1] = 'R1'\n",
    "                    elif dominoes[cur+1] == 'L1':\n",
    "                        dominoes[cur+1] = '.'\n",
    "            for i, d in enumerate(dominoes):\n",
    "                if d == 'L1':\n",
    "                    dominoes[i] = 'L'\n",
    "                    que.append((i, 'L'))\n",
    "                if d == 'R1':\n",
    "                    dominoes[i] = 'R'\n",
    "                    que.append((i, 'R'))\n",
    "        \n",
    "        return ''.join(dominoes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dom = list(dominoes)\n",
    "        q = collections.deque()\n",
    "        for i, d in enumerate(dom):\n",
    "            if d != '.':\n",
    "                q.append((i ,d))\n",
    "        while q:\n",
    "            i, d = q.popleft()\n",
    "            # left is the simple case if we loop from left to right\n",
    "            # other more complex cases are checked in right\n",
    "            if d == 'L' and i > 0 and dom[i - 1] == '.':\n",
    "                dom[i - 1] = 'L'\n",
    "                q.append((i-1, 'L'))\n",
    "            elif d == 'R':\n",
    "                if i + 1 < len(dom) and dom[i + 1] == '.':\n",
    "                    if i + 2 < len(dom) and dom[i + 2] == 'L':\n",
    "                        # this is the stuck case and the R.L pattern does not change, we need to pop the left to avoid double check\n",
    "                        q.popleft()\n",
    "                    else:\n",
    "                        dom[i + 1] = 'R'\n",
    "                        q.append((i + 1,'R'))\n",
    "        return ''.join(dom)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dom = list(dominoes)\n",
    "        q = collections.deque()\n",
    "\n",
    "        for i, n in enumerate(dom):\n",
    "            if n != '.':\n",
    "                q.append((i, n))\n",
    "\n",
    "        while q:\n",
    "            #一轮轮分析，因为多米诺也是一层层推的，对周围的影响是一步步的\n",
    "            i, n = q.popleft()\n",
    "            if i > 0 and dom[i] == 'L' and dom[i-1] == '.':\n",
    "                dom[i-1] = 'L' \n",
    "                q.append((i-1, 'L'))\n",
    "            elif n == 'R':\n",
    "                if i + 1 < len(dom) and dom[i+1] == '.':\n",
    "                    if i + 2 < len(dom) and dom[i+2] == 'L':\n",
    "                        q.popleft()\n",
    "                    else:\n",
    "                        q.append((i+1, 'R'))\n",
    "                        dom[i+1] = 'R'\n",
    "        return ''.join(dom)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        q=collections.deque()\n",
    "        n=len(dominoes)\n",
    "        dominoes=list(dominoes)\n",
    "\n",
    "        for i in range(n):\n",
    "            if dominoes[i]=='L' or dominoes[i]=='R':\n",
    "                q.append([i,dominoes[i]])\n",
    "        \n",
    "        while q:\n",
    "            size=len(q)\n",
    "            for i in range(size):\n",
    "                cur=q.popleft()\n",
    "                index,ch=cur[0],cur[1]\n",
    "                if ch=='L':\n",
    "                    if index-1>=0 and dominoes[index-1]=='.':\n",
    "                        if index-2<0 or dominoes[index-2]!='R':\n",
    "                            q.append([index-1,'L'])\n",
    "                           \n",
    "                if ch=='R':\n",
    "                    if index+1<n and dominoes[index+1]=='.':\n",
    "                        if index+2>=n or dominoes[index+2]!='L':\n",
    "                            q.append([index+1,'R'])\n",
    "            for index,ch in q:\n",
    "                dominoes[index]=ch\n",
    "\n",
    "        return ''.join(dominoes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        L, R = [], []\n",
    "        # 找出每个点，右边（包含当前位置）第一个 L 在哪儿\n",
    "        stack = collections.deque()\n",
    "        for i, x in enumerate(dominoes):\n",
    "            if x == 'L' or x == 'R':\n",
    "                stack.append(i)\n",
    "\n",
    "        for i, x in enumerate(dominoes):\n",
    "            while stack and stack[0] < i:\n",
    "                stack.popleft()\n",
    "            \n",
    "            if stack and dominoes[stack[0]] == 'L':\n",
    "                L.append(abs(stack[0] - i))\n",
    "            else:\n",
    "                L.append(float(\"inf\"))\n",
    "\n",
    "        # 找出每个点，左边（包含当前位置）第一个 R 在哪儿\n",
    "        stack = []\n",
    "        for i, x in enumerate(dominoes):\n",
    "            if x == 'R' or x == 'L':\n",
    "                stack.append(i)\n",
    "            if stack and dominoes[stack[-1]] == 'R':\n",
    "                R.append(abs(stack[-1]-i))\n",
    "            else:\n",
    "                R.append(float(\"inf\"))\n",
    "\n",
    "        ans = []\n",
    "        for i in range(len(dominoes)):\n",
    "            if L[i] < R[i]:\n",
    "                ans.append('L')\n",
    "            elif L[i] > R[i]:\n",
    "                ans.append('R')\n",
    "            else:\n",
    "                ans.append('.')\n",
    "        return ''.join(ans)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        N = len(dominoes)\n",
    "        dominoes = 'L' + dominoes + 'R'\n",
    "        stack = []\n",
    "        for i,ch in enumerate(dominoes):\n",
    "            if ch != '.':\n",
    "                stack.append((i, ch))\n",
    "        res = list(dominoes)\n",
    "        for i in range(len(stack)-1):\n",
    "            i1, d1 = stack[i]\n",
    "            i2, d2 = stack[i+1]\n",
    "            intv = i2-i1-1\n",
    "            if d1 == d2:\n",
    "                res[i1+1:i2] = d1*intv\n",
    "            else:\n",
    "                if d1 == 'L' and d2 == 'R':\n",
    "                    res[i1+1:i2] = '.'*intv\n",
    "                else:\n",
    "                    res[i1:i1+intv//2+1] = 'R'*(intv//2+1)\n",
    "                    res[i1+intv//2+1:i2] = 'L'*(i2-i1-1-intv//2)\n",
    "                    if intv%2 == 1:\n",
    "                        res[i1+intv//2+1] = '.'\n",
    "        return \"\".join(res[1:-1])\n",
    "                    \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dl = len(dominoes)\n",
    "        l = [0] * 2\n",
    "        r = [0] * 2\n",
    "        st = []\n",
    "        for i in range(0, dl):\n",
    "            c = dominoes[i]\n",
    "            if 'L' == c or 'R' == c:\n",
    "                if 'L' == c:\n",
    "                    l = [1, i]\n",
    "                else:\n",
    "                    if r[0] != 0:\n",
    "                        # print(f\"R {r[1]}, {i - 1}\")\n",
    "                        st.append(['R', r[1], i - 1])\n",
    "                    r = [1, i]\n",
    "                if l[0] > r[0]:\n",
    "                    if 0 == len(st):\n",
    "                        # print(f\"L F {0}, {l[1]}\")\n",
    "                        st.append(['L', 0, l[1]])\n",
    "                    else:\n",
    "                        # print(f\"L S {st[-1][2] + 1}, {l[1]}\")\n",
    "                        st.append(['L', st[-1][2] + 1, l[1]])\n",
    "                    r = [0] * 2\n",
    "                    l = [0] * 2\n",
    "                elif r[0] > 0 and r[0] == l[0]:\n",
    "                    # print(f\"B {r[1]}, {l[1]}\")\n",
    "                    st.append(['B', r[1], l[1]])\n",
    "                    r = [0] * 2\n",
    "                    l = [0] * 2\n",
    "        if r[0] > 0:\n",
    "            st.append([\"R\", r[1], dl - 1])\n",
    "\n",
    "        # print(st)\n",
    "        ret = \"\"\n",
    "        cur = 0\n",
    "        for r in st:\n",
    "            n = r[1]\n",
    "            # print(f\"cc {r}\")\n",
    "            if cur < n:\n",
    "                ret = ret + '.' * (n - cur)\n",
    "                cur = n\n",
    "            if 'L' == r[0]:\n",
    "                ret = ret + 'L' * (r[2] - n + 1)\n",
    "            elif 'R' == r[0]:\n",
    "                ret = ret + 'R' * (r[2] - n + 1)\n",
    "            else:\n",
    "                c = r[2] - n + 1\n",
    "                hf = c >> 1\n",
    "                ret = ret + \"R\" * hf\n",
    "                if c % 2 == 1:\n",
    "                    ret = ret + \".\"\n",
    "                ret = ret + \"L\" * hf\n",
    "\n",
    "            cur = r[2] + 1\n",
    "        if cur < dl:\n",
    "            ret = ret + '.' * (dl - cur)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        domi_len = len(dominoes)\n",
    "        stren_state = [0 for _ in range(domi_len)]\n",
    "        queue = collections.deque()\n",
    "        dominoes = list(dominoes)\n",
    "\n",
    "        for idx, item in enumerate(dominoes):\n",
    "            if item == '.': continue\n",
    "            direction = -1 if item == 'L' else 1\n",
    "            queue.append((idx, direction, 1))\n",
    "            stren_state[idx] = 1\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            loc, direct, time = node\n",
    "            next_loc = loc + direct\n",
    "\n",
    "            if next_loc < 0 or next_loc >= domi_len or dominoes[loc] == '.':\n",
    "                continue\n",
    "            \n",
    "            if stren_state[next_loc] == 0:\n",
    "                dominoes[next_loc] = 'L' if direct == -1 else 'R'\n",
    "                stren_state[next_loc] = time + 1\n",
    "                queue.append((next_loc, direct, time + 1))\n",
    "            \n",
    "            elif stren_state[next_loc] == time + 1:\n",
    "                dominoes[next_loc] = '.'\n",
    "        \n",
    "\n",
    "        return ''.join(dominoes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def val(self,l,start,end,char,ismid=False):\n",
    "        if ismid:\n",
    "            for i in range(start,end+1):\n",
    "                if i<start+(end+1-start)//2:\n",
    "                    l.append(char)\n",
    "                elif i==start+(end+1-start)//2 and (end+1-start)%2==1:\n",
    "                    l.append('.')\n",
    "                else:\n",
    "                    if char=='L':\n",
    "                        l.append('R')\n",
    "                    else:\n",
    "                        l.append('L')\n",
    "        else:\n",
    "            for i in range(start,end+1):\n",
    "                l.append(char)\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        if len(dominoes)==0:\n",
    "            return dominoes\n",
    "        indexlist = []\n",
    "        for i,char in enumerate(dominoes):\n",
    "            if char != '.':\n",
    "                indexlist.append((char,i))\n",
    "        if len(indexlist)==0:\n",
    "            return dominoes\n",
    "        indexlist.append(('.',len(dominoes)))\n",
    "        prev = ('.',-1)\n",
    "        out  = []\n",
    "        for (char,ind) in indexlist:\n",
    "            if prev[0]=='.':\n",
    "                if char=='L':\n",
    "                    self.val(out,prev[1]+1,ind,char,ismid=False)\n",
    "                elif char=='.':\n",
    "                    self.val(out,prev[1]+1,ind,char,ismid=False)\n",
    "                elif char=='R':\n",
    "                    self.val(out,prev[1]+1,ind-1,'.',ismid=False)\n",
    "                    out.append('R')\n",
    "            elif prev[0]=='L':\n",
    "                if char=='L':\n",
    "                    self.val(out,prev[1]+1,ind,char,ismid=False)\n",
    "                elif char=='.':\n",
    "                    self.val(out,prev[1]+1,ind,char,ismid=False)\n",
    "                elif char=='R':\n",
    "                    self.val(out,prev[1]+1,ind-1,'.',ismid=False)\n",
    "                    out.append('R')\n",
    "            elif prev[0]=='R':\n",
    "                if char=='L':\n",
    "                    del out[-1]\n",
    "                    self.val(out,prev[1],ind,'R',ismid=True)\n",
    "                elif char=='.':\n",
    "                    self.val(out,prev[1]+1,ind,'R',ismid=False)\n",
    "                elif char=='R':\n",
    "                    self.val(out,prev[1]+1,ind,'R',ismid=False)\n",
    "            prev = (out[-1],len(out)-1)\n",
    "        return \"\".join(out[:-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dMap={\n",
    "        \"BL\":[\"L\",1,\"\"],\n",
    "        \"BR\":[\".\",0,\"R\"],\n",
    "        \"LR\":[\".\",0,\"R\"],\n",
    "        \"RR\":[\"R\",1,\"\"],\n",
    "        \"LL\":[\"L\",1,\"\"],\n",
    "        \"LE\":[\".\",0,\"\"],\n",
    "        \"RE\":[\"R\",0,\"\"],\n",
    "        \"BE\":[\".\",1,\"\"]\n",
    "    }\n",
    "\n",
    "    def check(self, c):\n",
    "        b = c[0]\n",
    "        e = c[1]\n",
    "        cc = b + e\n",
    "        l = c[2] + 1 if b == \"B\" or e == \"E\" else c[2]\n",
    "        if cc == \"RL\":\n",
    "            n = l // 2\n",
    "            return \"R\" * n + \".\"*(l%2) + \"L\" * (n + 1)\n",
    "        else:\n",
    "            d = self.dMap[cc]\n",
    "            return d[0]*(l+d[1])+d[2]\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "\n",
    "        n = len(dominoes)\n",
    "        if n == 1:\n",
    "            return dominoes\n",
    "        s = []\n",
    "        s.append([\"B\"]) if dominoes[0] == \".\" else s.append([dominoes[0]])\n",
    "\n",
    "        k = 0\n",
    "        i=0\n",
    "        for i in range(1, n - 1):\n",
    "            if dominoes[i] == \".\":\n",
    "                k += 1\n",
    "            else:\n",
    "                s[-1].append(dominoes[i])\n",
    "                s[-1].append(k)\n",
    "                k = 0\n",
    "                s.append([dominoes[i]])\n",
    "        i+=1\n",
    "        s[-1].append(\"E\") if dominoes[i] == \".\" else s[-1].append(dominoes[i])\n",
    "        s[-1].append(k)\n",
    "        if s[0][0] !=\"B\":\n",
    "            result = s[0][0]\n",
    "        else:\n",
    "            result = \"\"\n",
    "        for i in s:\n",
    "            result += self.check(i)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        s = list(dominoes)\n",
    "        n = len(s)\n",
    "        q = deque() \n",
    "        g = [0] * n\n",
    "        for i, x in enumerate(s):\n",
    "            if x != '.':\n",
    "                d = 1 if x == 'R' else -1\n",
    "                q.append((i, 1, d))\n",
    "                g[i] = 1\n",
    "        while q:\n",
    "            p, t, d = q.popleft()\n",
    "            np = p + d\n",
    "            if s[p] == '.' or np < 0 or np >= n: continue\n",
    "            if not g[np]:\n",
    "                q.append((np, t + 1, d))\n",
    "                g[np] = t + 1\n",
    "                s[np] = 'R' if d == 1 else 'L'\n",
    "            elif g[np] == t + 1:\n",
    "                s[np] = '.'\n",
    "            \n",
    "        return ''.join(s)\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        \n",
    "        length = len(dominoes)\n",
    "        F_state = [0 for _ in range(length)]\n",
    "        queue = collections.deque()\n",
    "        dominoes = list(dominoes)\n",
    "\n",
    "        for idx, item in enumerate(dominoes):\n",
    "            if item == '.': continue\n",
    "            direction = -1 if item == 'L' else 1\n",
    "            queue.append((idx, direction, 1))\n",
    "            F_state[idx] = 1\n",
    "\n",
    "        while queue:\n",
    "\n",
    "            node = queue.popleft()\n",
    "            loc, direction, time = node\n",
    "            nxt = loc + direction\n",
    "\n",
    "            if nxt < 0 or nxt >= length or dominoes[loc] == '.':\n",
    "                continue\n",
    "            \n",
    "            if F_state[nxt] == 0:\n",
    "                dominoes[nxt] = 'L' if direction == -1 else 'R'\n",
    "                queue.append((nxt, direction, time + 1))\n",
    "                F_state[nxt] = time + 1\n",
    "            elif F_state[nxt] == time + 1:\n",
    "                dominoes[nxt] = '.'\n",
    "\n",
    "        return ''.join(dominoes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dominoes_list = list(dominoes)\n",
    "        n = len(dominoes_list)\n",
    "        q = deque()\n",
    "        for i, domino in enumerate(dominoes_list):\n",
    "            if domino != '.':\n",
    "                q.append((i, domino))\n",
    "        while(q):\n",
    "            qSize = len(q)\n",
    "            h = set()\n",
    "            for _ in range(qSize):\n",
    "                i, direction = q.popleft()\n",
    "                if direction == 'L':\n",
    "                    n_i = i-1\n",
    "                    if n_i >= 0 and dominoes_list[n_i] == '.':\n",
    "                        h.add((n_i, 'L'))\n",
    "                elif direction == 'R':\n",
    "                    n_i = i+1\n",
    "                    if n_i < n and dominoes_list[n_i] == '.':\n",
    "                        h.add((n_i, 'R'))\n",
    "            for pair in h:\n",
    "                n_i = pair[0]\n",
    "                if (n_i, 'L') in h and (n_i, 'R') in h:\n",
    "                    continue\n",
    "                else:\n",
    "                    dominoes_list[n_i] = pair[1]\n",
    "                    q.append(pair)\n",
    "        return \"\".join(dominoes_list)\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dominoes = ['L'] + list(dominoes) + ['R']\n",
    "        queue = deque()\n",
    "        for i in range(1, len(dominoes) - 1):\n",
    "            if dominoes[i] != '.':\n",
    "                queue.append((i, dominoes[i]))\n",
    "        \n",
    "        \n",
    "        while queue:\n",
    "            vis = set()\n",
    "            for i in range(len(queue)):\n",
    "                index, char = queue.popleft()\n",
    "                if char == 'L':\n",
    "                    if dominoes[index - 1] == '.':\n",
    "                        dominoes[index - 1] = 'L'\n",
    "                        vis.add(index - 1)\n",
    "                        queue.append((index - 1, 'L'))\n",
    "                    elif index - 1 in vis:\n",
    "                        dominoes[index - 1] = '|'\n",
    "\n",
    "                elif char == 'R':\n",
    "                    if dominoes[index + 1] == '.':\n",
    "                        dominoes[index + 1] = 'R'\n",
    "                        vis.add(index + 1)\n",
    "                        queue.append((index + 1, 'R'))\n",
    "                    elif index + 1 in vis:\n",
    "                        dominoes[index + 1] = '|'\n",
    "                   \n",
    "                \n",
    "        \n",
    "        return \"\".join(dominoes[1:-1]).replace('|', '.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # BFS\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dominoes_list = list(dominoes)\n",
    "        n = len(dominoes_list)\n",
    "        q = deque()\n",
    "        for i, domino in enumerate(dominoes_list):\n",
    "            if domino != '.':\n",
    "                q.append((i, domino))\n",
    "        while(q):\n",
    "            qSize = len(q)\n",
    "            h = set()\n",
    "            for _ in range(qSize):\n",
    "                i, direction = q.popleft()\n",
    "                if direction == 'L':\n",
    "                    n_i = i-1\n",
    "                    if n_i >= 0 and dominoes_list[n_i] == '.':\n",
    "                        h.add((n_i, 'L'))\n",
    "                elif direction == 'R':\n",
    "                    n_i = i+1\n",
    "                    if n_i < n and dominoes_list[n_i] == '.':\n",
    "                        h.add((n_i, 'R'))\n",
    "            for pair in h:\n",
    "                n_i = pair[0]\n",
    "                if (n_i, 'L') in h and (n_i, 'R') in h:\n",
    "                    continue\n",
    "                else:\n",
    "                    dominoes_list[n_i] = pair[1]\n",
    "                    q.append(pair)\n",
    "        return \"\".join(dominoes_list)\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dominoes_list = list(dominoes)\n",
    "        n = len(dominoes_list)\n",
    "        q = deque()\n",
    "        for i, domino in enumerate(dominoes_list):\n",
    "            if domino != '.':\n",
    "                q.append((i, domino))\n",
    "        while(q):\n",
    "            qSize = len(q)\n",
    "            h = set()\n",
    "            for _ in range(qSize):\n",
    "                i, direction = q.popleft()\n",
    "                if direction == 'L':\n",
    "                    n_i = i-1\n",
    "                    if n_i >= 0 and dominoes_list[n_i] == '.':\n",
    "                        h.add((n_i, 'L'))\n",
    "                elif direction == 'R':\n",
    "                    n_i = i+1\n",
    "                    if n_i < n and dominoes_list[n_i] == '.':\n",
    "                        h.add((n_i, 'R'))\n",
    "            for pair in h:\n",
    "                n_i = pair[0]\n",
    "                if (n_i, 'L') in h and (n_i, 'R') in h:\n",
    "                    continue\n",
    "                else:\n",
    "                    dominoes_list[n_i] = pair[1]\n",
    "                    q.append(pair)\n",
    "        return \"\".join(dominoes_list)\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        tmp = \"\"\n",
    "        while dominoes != tmp:\n",
    "            tmp = dominoes\n",
    "            dominoes = dominoes.replace(\"R.L\", \"T\")\n",
    "            dominoes = dominoes.replace(\".L\", \"LL\")\n",
    "            dominoes = dominoes.replace(\"R.\", \"RR\")\n",
    "            dominoes = dominoes.replace(\"T\", \"R.L\")\n",
    "        return dominoes\n",
    "        \n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        mask = []\n",
    "        n = len(dominoes)\n",
    "        for i, d in enumerate(dominoes):\n",
    "            if d != '.':\n",
    "                mask.append((i, d))\n",
    "        dominoes = list(dominoes)\n",
    "        mask = [(-1, 'L')] + mask + [(n, 'R')]\n",
    "        for i, (x, y) in enumerate(mask):\n",
    "            if y == 'L':\n",
    "                if i:\n",
    "                    if mask[i-1][1] == 'R':\n",
    "                        for j in range((x - mask[i-1][0] + 1) >> 1):\n",
    "                            dominoes[x - j] = 'L'\n",
    "                    else:\n",
    "                        for j in range(x - mask[i-1][0]):\n",
    "                            dominoes[x - j] = 'L'\n",
    "            else:\n",
    "                if i + 1 < len(mask):\n",
    "                    if mask[i+1][1] == 'L':\n",
    "                        for j in range((mask[i+1][0] - x + 1) >> 1):\n",
    "                            dominoes[x + j] = 'R'\n",
    "                    else:\n",
    "                        for j in range(mask[i+1][0] - x):\n",
    "                            dominoes[x + j] = 'R'\n",
    "        print(dominoes)\n",
    "        return ''.join(dominoes)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        inoes=list(dominoes)\n",
    "        dp=[['',''] for i in range(len(dominoes))]\n",
    " \n",
    "        for i in range(len(inoes)):\n",
    "            if inoes[i]=='L':\n",
    "                dp[i]=['L','L']\n",
    "            elif inoes[i]=='R':\n",
    "                dp[i]=['R','R']\n",
    " \n",
    "        break_falg=False\n",
    "        flag=False\n",
    "        while True:\n",
    "\n",
    "            for i in range(len(inoes)):\n",
    "                if dp[i][0]!='':\n",
    "                    flag=False\n",
    "                    continue\n",
    "                if i>0 and flag==False and dp[i][0]=='' and dp[i-1][1]=='R':\n",
    "                    dp[i][0]='R'\n",
    "                    flag=True\n",
    "                    break_falg=True\n",
    "                if i+1<len(inoes) and dp[i][1]=='' and dp[i+1][0]=='L':\n",
    "                    dp[i][1]='L'\n",
    "                    break_falg = True\n",
    "\n",
    "                if dp[i][0]=='' and dp[i][1]!='':\n",
    "                    dp[i][0]=dp[i][1]\n",
    "                if dp[i][1]=='' and dp[i][0]!='':\n",
    "                    dp[i][1]=dp[i][0]\n",
    "\n",
    "\n",
    "            if break_falg==True:\n",
    "                break_falg = False\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        r=''\n",
    "        for i in range(len(dp)):\n",
    "            if dp[i][0]==dp[i][1]:\n",
    "                if dp[i][0]=='':\n",
    "                    r+='.'\n",
    "                else:\n",
    "                    r+=dp[i][0]\n",
    "            else:\n",
    "                r+='.'\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dominoes = list(dominoes)\n",
    "        decided = set()\n",
    "        falling = {}\n",
    "\n",
    "        flag = True\n",
    "        while (flag):\n",
    "            flag = False\n",
    "            for i in range(len(dominoes)):\n",
    "                if i in decided: continue\n",
    "\n",
    "                if (dominoes[i] == '.'):\n",
    "                    if (i > 0 and i < len(dominoes) - 1):\n",
    "                        if (dominoes[i-1] == 'R' and dominoes[i+1] == 'L'):\n",
    "                            decided.add(i)\n",
    "                        elif (dominoes[i-1] == 'R'):\n",
    "                            falling[i] = 'R'\n",
    "                            decided.add(i)\n",
    "                            flag = True\n",
    "                        elif (dominoes[i+1] == 'L'):\n",
    "                            falling[i] = 'L'\n",
    "                            decided.add(i)\n",
    "                            flag = True\n",
    "                    elif (i > 0 and dominoes[i-1] == 'R'):\n",
    "                        falling[i] = 'R'\n",
    "                        decided.add(i)\n",
    "                        flag = True\n",
    "                    elif (i < len(dominoes) - 1 and dominoes[i+1] == 'L'):\n",
    "                        falling[i] = 'L'\n",
    "                        decided.add(i)\n",
    "                        flag = True\n",
    "                else:\n",
    "                    decided.add(i)\n",
    "            for key in falling:\n",
    "                dominoes[key] = falling[key]\n",
    "            falling = {}\n",
    "            \n",
    "        return ''.join(dominoes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dominoes = list(dominoes)\n",
    "        n = len(dominoes)\n",
    "        status = [[0,0] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if dominoes[i] == 'L':\n",
    "                status[i][0] =n\n",
    "                j = i - 1\n",
    "                while j >= 0 and dominoes[j] == '.':\n",
    "                    status[j][0] = status[j+1][0] - 1\n",
    "                    j -= 1\n",
    "            elif dominoes[i] == 'R':\n",
    "                status[i][1] = n\n",
    "                j = i + 1\n",
    "                while j < n and dominoes[j] == '.':\n",
    "                    status[j][1] =status[j-1][1] - 1\n",
    "                    j += 1\n",
    "        for i in range(n):\n",
    "            left,right = status[i][0],status[i][1]\n",
    "            if left == right:\n",
    "                dominoes[i] = '.'\n",
    "            elif left > right:dominoes[i] = 'L'\n",
    "            else: dominoes[i] = 'R'\n",
    "        return ''.join(dominoes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        q, ans = deque(), ['.' for _ in range(len(dominoes))]\n",
    "        for i in range(len(dominoes)):\n",
    "            if dominoes[i] != '.':\n",
    "                q.append((i, dominoes[i], 0))\n",
    "        times = [len(dominoes) for _ in range(len(dominoes))]\n",
    "\n",
    "        while q:\n",
    "            i, direction, time = q.popleft()\n",
    "            if times[i] == time:\n",
    "                ans[i] = '.'\n",
    "                continue\n",
    "            elif times[i] < time:\n",
    "                continue\n",
    "            else:\n",
    "                times[i] = time\n",
    "            \n",
    "            if direction == 'L':\n",
    "                ans[i] = 'L'\n",
    "                if i-1 >= 0 and dominoes[i-1] == '.':\n",
    "                    q.append((i-1, 'L', time+1))\n",
    "            else:\n",
    "                ans[i] = 'R'\n",
    "                if i+1 < len(dominoes) and dominoes[i+1] == '.':\n",
    "                    q.append((i+1, 'R', time+1))\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        ans = \"\"\n",
    "        length = len(dominoes)\n",
    "        tmp = \".\" + dominoes + \".\"\n",
    "        for i in range(1, length + 1):\n",
    "            if tmp[i] == \".\":\n",
    "                if tmp[i - 1] == 'R':\n",
    "                    if tmp[i + 1] != 'L':\n",
    "                        ans += \"R\"\n",
    "                    else:\n",
    "                        ans += \".\"\n",
    "                elif tmp[i+1] == \"L\":\n",
    "                    ans += \"L\"\n",
    "                else:\n",
    "                    ans += \".\"\n",
    "            else:\n",
    "                ans += tmp[i]\n",
    "        \n",
    "        return self.pushDominoes(ans) if ans != dominoes else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        q=deque()\n",
    "        length=len(dominoes)\n",
    "        ret=[]\n",
    "        for i in range(length):\n",
    "            if dominoes[i]==\"R\":\n",
    "                q.append([i,\"R\"])\n",
    "            elif dominoes[i]==\"L\":\n",
    "                q.append([i,\"L\"])\n",
    "            ret.append(dominoes[i])\n",
    "        while q:\n",
    "            l=len(q)\n",
    "            new=set()\n",
    "            for i in range(l):\n",
    "                p,d=q.popleft()\n",
    "                if d==\"R\":\n",
    "                    if (p+1,\"L\") in new:new.remove((p+1,\"L\"))\n",
    "                    elif p+1<length and  ret[p+1]==\".\":new.add((p+1,\"R\"))\n",
    "                else:\n",
    "                    if (p-1,\"R\") in new:new.remove((p-1,\"R\"))\n",
    "                    elif p-1>=0 and ret[p-1]==\".\":new.add((p-1,\"L\"))\n",
    "            for n in new:\n",
    "                ret[n[0]]=n[1]\n",
    "                q.append(list(n))\n",
    "        return \"\".join(ret)\n",
    "\n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        rs_list = list(dominoes)\n",
    "\n",
    "        visited = set()\n",
    "        to_fall_list = []\n",
    "        for index, value in enumerate(rs_list):\n",
    "            if value != \".\":\n",
    "                to_fall_list.append(index)\n",
    "\n",
    "        # print(rs_list[17:21])\n",
    "        while len(visited) != len(rs_list) and len(to_fall_list)>0:\n",
    "            # print(to_fall_list)\n",
    "            tmp_list = to_fall_list.copy()\n",
    "            to_fall_list = []\n",
    "            jump = False\n",
    "            for index, value in enumerate(tmp_list):\n",
    "                if jump:\n",
    "                    jump = False\n",
    "                    continue\n",
    "                \n",
    "                visited.add(value)\n",
    "                # print(value, rs_list[value])\n",
    "                if rs_list[value] == \"L\":\n",
    "                    # print(value)\n",
    "                    if value > 0:\n",
    "                        if rs_list[value-1] == \".\":\n",
    "                            \n",
    "                            rs_list[value-1] = \"L\"\n",
    "                            to_fall_list.append(value-1)\n",
    "                elif rs_list[value] == \"R\":\n",
    "                    if value < len(rs_list) - 1:\n",
    "                        if rs_list[value+1] == \".\":\n",
    "                            if index+1<len(tmp_list):\n",
    "                                if tmp_list[index+1] == value + 2 and rs_list[value+2] == \"L\":\n",
    "                                    jump = True\n",
    "                                    continue\n",
    "                            rs_list[value+1] = \"R\"\n",
    "                            to_fall_list.append(value+1)\n",
    "        return \"\".join(rs_list)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        # def move(d_):\n",
    "        #     rs_str = \"\"\n",
    "        #     for index, ch in enumerate(d_):\n",
    "        #         if ch in [\"L\", \"R\"]:\n",
    "        #             rs_str = f\"{rs_str}{ch}\"\n",
    "        #             continue\n",
    "\n",
    "        #         left = \".\"\n",
    "        #         if index > 0:\n",
    "        #             left = d_[index-1]\n",
    "        #         right = \".\"\n",
    "        #         if index < len(d_)-1:\n",
    "        #             right = d_[index+1]\n",
    "        #         if left == \"R\" and right != \"L\":\n",
    "        #             rs_str = f\"{rs_str}R\"\n",
    "        #         elif left != \"R\" and right == \"L\":\n",
    "        #             rs_str = f\"{rs_str}L\"\n",
    "        #         else:\n",
    "        #             rs_str = f\"{rs_str}.\"\n",
    "        #         # if left == \".\" and right == \".\":\n",
    "        #         #     rs_str = f\"{rs_str}.\"\n",
    "        #         # elif left == \"L\"\n",
    "        #     return rs_str\n",
    "\n",
    "\n",
    "        # new_state = dominoes\n",
    "        # last_state = \"\"\n",
    "        # while last_state != new_state:\n",
    "        #     last_state = new_state\n",
    "        #     new_state = move(new_state)\n",
    "        # return new_state\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        dominoes = list(dominoes)\n",
    "        n = len(dominoes)\n",
    "        q = [(i, x) for i, x in enumerate(dominoes) if x != '.']\n",
    "        vis = set() # 每一层的访问  非全局  逐层记录并及时clear() 这样可以当做判断是否一块板子“同一层(同一时间)”两边受力\n",
    "        tmp = []\n",
    "        while q:\n",
    "            for i, x in q:\n",
    "                j = i - 1 if x =='L' else i + 1\n",
    "                if 0 <= j < n:\n",
    "                    y = dominoes[j]\n",
    "                    if y == '.': # 碰到树立的就倒下\n",
    "                        tmp.append((j, x))\n",
    "                        dominoes[j] = x\n",
    "                        vis.add(j)\n",
    "                    elif j in vis and x != y: # 同一时间两边受力\n",
    "                        dominoes[j] = '.'\n",
    "            q = tmp[:]\n",
    "            tmp.clear()\n",
    "            vis.clear()\n",
    "        return ''.join(dominoes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n = len(dominoes)\n",
    "        # [L_dist, R_dist]\n",
    "        records = [[inf, inf] for _ in range(n)]\n",
    "        cur = -inf\n",
    "        for i, c in enumerate(dominoes):\n",
    "            if c == 'R':\n",
    "                cur = i\n",
    "            elif c == 'L':\n",
    "                cur = -inf\n",
    "            records[i][1] = i - cur\n",
    "        cur = inf\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if dominoes[i] == 'L':\n",
    "                cur = i\n",
    "            elif dominoes[i] == 'R':\n",
    "                cur = inf\n",
    "            records[i][0] = cur - i\n",
    "        return \"\".join('.' if l == r else ('R' if l > r else 'L') for l, r in records)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        domino_list = [s for s in dominoes]\n",
    "        q = []\n",
    "        first_change = [0 for _ in range(len(dominoes))]\n",
    "        for i in range(len(domino_list)):\n",
    "            if domino_list[i] == \"L\":\n",
    "                q.append((i, 1, -1))\n",
    "                first_change[i] = 1\n",
    "            elif domino_list[i] == \"R\":\n",
    "                q.append((i, 1, +1))\n",
    "                first_change[i] = 1\n",
    "            \n",
    "        \n",
    "        q = collections.deque(q)\n",
    "        seen = set(q)\n",
    "\n",
    "        total_time = 0\n",
    "        while q:\n",
    "            total_time += 1\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                loc, time, direction = q.popleft()\n",
    "                ne = loc + direction\n",
    "                if ne < 0 or ne>=len(domino_list) or domino_list[loc]==\".\": continue\n",
    "                if first_change[ne] == 0:\n",
    "                    q.append((ne, time+1, direction))\n",
    "                    first_change[ne] = time+1\n",
    "                    if direction==-1: domino_list[ne]=\"L\"\n",
    "                    elif direction==1: domino_list[ne]=\"R\"\n",
    "                elif first_change[ne] == time+1:\n",
    "                    domino_list[ne]=\".\"\n",
    "        res = ''\n",
    "        for i in domino_list:\n",
    "            res+=i\n",
    "        return res\n",
    "\n",
    "\n",
    "        # domino_list = [s for s in dominoes]\n",
    "        # q = []\n",
    "        # for i in range(len(domino_list)):\n",
    "        #     if domino_list[i] != \".\":\n",
    "        #         q.append(i)\n",
    "        # q = collections.deque(q)\n",
    "        # seen = set(q)\n",
    "\n",
    "        # while q:\n",
    "        #     size = len(q)\n",
    "        #     for _ in range(size):\n",
    "        #         ind = q.popleft()\n",
    "        #         print(q)\n",
    "        #         print(domino_list)\n",
    "        #         if domino_list[ind] == \"L\" and ind > 0:\n",
    "        #             if domino_list[ind - 1] == \".\":\n",
    "        #                 domino_list[ind-1] = \"L\"\n",
    "        #                 q.append(ind-1)\n",
    "        #             elif domino_list[ind - 1] == \"L\":\n",
    "        #                 continue\n",
    "        #             elif domino_list[ind-1] == \"R\":\n",
    "        #                 domino_list[ind] = \".\"\n",
    "        #                 domino_list[ind-1]=\".\"\n",
    "        #         if domino_list[ind] == \"L\" and ind == 0:\n",
    "        #             continue\n",
    "\n",
    "        #         if domino_list[ind] == \"R\" and ind < len(domino_list)-1:\n",
    "        #             if domino_list[ind + 1] == \".\":\n",
    "        #                 domino_list[ind+1] = \"R\"\n",
    "        #                 q.append(ind+1)\n",
    "        #             elif domino_list[ind + 1] == \"R\":\n",
    "        #                 continue\n",
    "        #             elif domino_list[ind+1] == \"L\":\n",
    "        #                 domino_list[ind] = \".\"\n",
    "        #                 domino_list[ind+1]=\".\"\n",
    "        #         if domino_list[ind] == \"R\" and ind == len(domino_list)-1:\n",
    "        #             continue\n",
    "        # res = ''\n",
    "        # for i in domino_list:\n",
    "        #     res+=i\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "\n",
    "        n = len(dominoes)\n",
    "\n",
    "        records = [[inf, inf] for _ in range(n)]\n",
    "\n",
    "        cur = -inf\n",
    "\n",
    "        for i, c in enumerate(dominoes):\n",
    "\n",
    "            if c == \"R\":\n",
    "                cur = i\n",
    "            elif c == \"L\":\n",
    "\n",
    "                cur = -inf\n",
    "\n",
    "            records[i][0] = i - cur\n",
    "        cur = inf\n",
    "        for i in range(n-1, -1, -1):\n",
    "\n",
    "            if dominoes[i] == \"L\":\n",
    "\n",
    "                cur = i\n",
    "            elif dominoes[i] == \"R\":\n",
    "                cur = inf\n",
    "            records[i][1] = cur - i\n",
    "\n",
    "        return \"\".join(\".\" if l == r else ('R' if l > r else 'L') for r, l in records)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n = len(dominoes)\n",
    "        q = deque()\n",
    "        time = [-1] * n\n",
    "        force = [[] for _ in range(n)]\n",
    "        for i, f in enumerate(dominoes):\n",
    "            if f != '.':\n",
    "                q.append(i)\n",
    "                time[i] = 0\n",
    "                force[i].append(f)\n",
    "\n",
    "        res = ['.'] * n\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            if len(force[i]) == 1:\n",
    "                res[i] = f = force[i][0]\n",
    "                ni = i - 1 if f == 'L' else i + 1\n",
    "                if 0 <= ni < n:\n",
    "                    t = time[i]\n",
    "                    if time[ni] == -1:\n",
    "                        q.append(ni)\n",
    "                        time[ni] = t + 1\n",
    "                        force[ni].append(f)\n",
    "                    elif time[ni] == t + 1:\n",
    "                        force[ni].append(f)\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "      \n",
    "        n = len(dominoes)\n",
    "        times = [-1 for _ in range(n)]        \n",
    "        forces = [[] for _ in range(n)]\n",
    "        q = deque()\n",
    "        res = [\".\" for _ in range(n)]\n",
    "        for idx, a in enumerate(dominoes):\n",
    "            if a != '.':\n",
    "                q.append(idx)\n",
    "                times[idx] = 0\n",
    "                forces[idx].append(a)\n",
    "\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            if len(forces[i]) == 1:\n",
    "                res[i] = forces[i][0]\n",
    "                next = -1\n",
    "                if res[i] == \"L\":\n",
    "                    next = i - 1\n",
    "                else:\n",
    "                    next = i + 1\n",
    "                # q.append(i)\n",
    "                if 0 <= next and next < n:\n",
    "                    t = times[next]\n",
    "                    if t == -1:\n",
    "                        q.append(next)\n",
    "                        times[next] = times[i] + 1\n",
    "                        forces[next].append(res[i])\n",
    "                \n",
    "                    elif t == times[i] + 1:\n",
    "                        forces[next].append(res[i])\n",
    "        return ''.join(res)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n = len(dominoes)\n",
    "        # [L_dist, R_dist]\n",
    "        records = [[inf, inf] for _ in range(n)]\n",
    "        cur = -inf\n",
    "        for i, c in enumerate(dominoes):\n",
    "            if c == 'R':\n",
    "                cur = i\n",
    "            elif c == 'L':\n",
    "                cur = -inf\n",
    "            records[i][1] = i - cur\n",
    "        cur = inf\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if dominoes[i] == 'L':\n",
    "                cur = i\n",
    "            elif dominoes[i] == 'R':\n",
    "                cur = inf\n",
    "            records[i][0] = cur - i\n",
    "        return \"\".join('.' if l == r else ('R' if l > r else 'L') for l, r in records)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        queue = deque()\n",
    "        n = len(dominoes)\n",
    "        force = [[] for i in range(n)]\n",
    "        time = [-1 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if dominoes[i] != '.':\n",
    "                force[i].append(dominoes[i])\n",
    "                time[i] = 0\n",
    "                queue.append(i)\n",
    "        res = ['.' for i in range(n)]\n",
    "        while queue:\n",
    "            i = queue.popleft()\n",
    "            if len(force[i]) <= 1:\n",
    "                next_index = i - 1 if force[i][0] == 'L' else i + 1\n",
    "                res[i] = force[i][0]\n",
    "                f = force[i][0]\n",
    "                print(next_index)\n",
    "                if 0 <= next_index < n:\n",
    "                    cur_time = time[i]\n",
    "                    if time[next_index] == -1:\n",
    "                        force[next_index].append(f)\n",
    "                        time[next_index] = cur_time + 1\n",
    "                        queue.append(next_index)\n",
    "                    elif time[next_index] == cur_time + 1:\n",
    "                        force[next_index].append(f)\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n = len(dominoes)\n",
    "        #[L_dist, R_dist]\n",
    "        records = [[math.inf,math.inf] for _ in range(n)]\n",
    "        \n",
    "        cur = -math.inf\n",
    "        for i,c in enumerate(dominoes):\n",
    "            if c=='R':\n",
    "                cur = i\n",
    "            elif c =='L':\n",
    "                cur = -math.inf\n",
    "            records[i][1]=i-cur\n",
    "\n",
    "        cur = math.inf\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if dominoes[i]=='L':\n",
    "                cur = i\n",
    "            elif dominoes[i]=='R':\n",
    "                cur = math.inf\n",
    "            records[i][0] = cur-i\n",
    "        \n",
    "        result = []\n",
    "        for l,r in records:\n",
    "            if l == r:\n",
    "                result.append('.')\n",
    "            elif l > r:\n",
    "                result.append('R')\n",
    "            else:\n",
    "                result.append('L')\n",
    "\n",
    "        return \"\".join(result)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n = len(dominoes)\n",
    "        # [L_dist, R_dist]\n",
    "        records = [[inf, inf] for _ in range(n)]\n",
    "        cur = -inf\n",
    "        for i, c in enumerate(dominoes):\n",
    "            if c == 'R':\n",
    "                cur = i\n",
    "            elif c == 'L':\n",
    "                cur = -inf\n",
    "            records[i][1] = i - cur\n",
    "        cur = inf\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if dominoes[i] == 'L':\n",
    "                cur = i\n",
    "            elif dominoes[i] == 'R':\n",
    "                cur = inf\n",
    "            records[i][0] = cur - i\n",
    "        return \"\".join('.' if l == r else ('R' if l > r else 'L') for l, r in records)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n = len(dominoes)\n",
    "        queue = deque()\n",
    "        time = [-1 for _ in range(n)]\n",
    "        force = [[] for _ in range(n)]\n",
    "        \n",
    "        for i, d in enumerate(dominoes):\n",
    "            if d != '.':\n",
    "                queue.append(i)\n",
    "                time[i] = 0\n",
    "                force[i].append(d)\n",
    "        \n",
    "        ans = ['.' for _ in range(n)]\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            cur = queue.popleft()\n",
    "\n",
    "            # 至受一个力才会倒\n",
    "            if len(force[cur]) == 1:\n",
    "\n",
    "                ans[cur] = d = force[cur][0]\n",
    "\n",
    "                # 施加力的下一个骨牌\n",
    "                nxt_d = cur - 1 if d == 'L' else cur + 1\n",
    "\n",
    "                if 0 <= nxt_d < n:\n",
    "                    t = time[cur]\n",
    "\n",
    "                    if time[nxt_d] == -1: # 没有被推倒\n",
    "                        queue.append(nxt_d)\n",
    "                        time[nxt_d] = t + 1     # 时间是cur的时间+1\n",
    "                        force[nxt_d].append(d)  # 受到一个来自cur的力\n",
    "\n",
    "                    elif time[nxt_d] == t + 1:  # 可能受到另一个骨牌推动了，且时间刚好相等\n",
    "                        force[nxt_d].append(d)\n",
    "\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def pushDominoes(self, dominoes: str) -> str:\r\n",
    "        n = len(dominoes)\r\n",
    "        q = deque()\r\n",
    "        time = [-1] * n\r\n",
    "        force = [[] for _ in range(n)]\r\n",
    "        for i, f in enumerate(dominoes):\r\n",
    "            if f != '.':\r\n",
    "                q.append(i)\r\n",
    "                time[i] = 0\r\n",
    "                force[i].append(f)\r\n",
    "\r\n",
    "        res = ['.'] * n\r\n",
    "        while q:\r\n",
    "            i = q.popleft()\r\n",
    "            if len(force[i]) == 1:\r\n",
    "                res[i] = f = force[i][0]\r\n",
    "                ni = i - 1 if f == 'L' else i + 1\r\n",
    "                if 0 <= ni < n:\r\n",
    "                    t = time[i]\r\n",
    "                    if time[ni] == -1:\r\n",
    "                        q.append(ni)\r\n",
    "                        time[ni] = t + 1\r\n",
    "                        force[ni].append(f)\r\n",
    "                    elif time[ni] == t + 1:\r\n",
    "                        force[ni].append(f)\r\n",
    "        return ''.join(res)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pushDominoes(self, dominoes: str) -> str:\n",
    "        n = len(dominoes)\n",
    "        q = deque()\n",
    "        time =[-1]*n\n",
    "        f = [[] for _ in range(n)]\n",
    "        for i,x in enumerate(dominoes):\n",
    "            if x!='.':\n",
    "                q.append(i)\n",
    "                time[i]=0\n",
    "                f[i].append(x) # 第i个dominoes 的受力\n",
    "        \n",
    "        ans = ['.']*n\n",
    "\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            if len(f[i]) == 1:\n",
    "                ans[i] = x = f[i][0]\n",
    "                ni =i -1 if x =='L' else i+1\n",
    "                if 0<=ni<n:\n",
    "                    t = time[i]\n",
    "                    if time[ni] == -1:\n",
    "                        q.append(ni)\n",
    "                        f[ni].append(x)\n",
    "                        time[ni]= t+1\n",
    "                    elif time[ni]==t+1:\n",
    "                        f[ni].append(x)\n",
    "        return ''.join(ans)\n",
    "\n",
    "\n",
    "                        \n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
